//
// Created by jizhe hu on 2024/3/6.
//

#ifndef LEETCODE_HOT100_H
#define LEETCODE_HOT100_H

#include "string"
#include <set>
#include <list>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;

//! 2. 两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* head = new ListNode;
    ListNode* res = head;
    bool flag = false;
    while(l1 && l2) {
        res->next = new ListNode;

        res->next->val = l1->val + l2->val;
        if(flag) res->next->val += 1;
        if(res->next->val >= 10) {
            res->next->val -= 10;
            flag = true;
        } else {
            flag = false;
        }
        res = res->next;
        l1 = l1->next;
        l2 = l2->next;
    }
    ListNode* l = nullptr;
    if(l1) l = l1;
    if(l2) l = l2;
    while(l) {
        res->next = new ListNode;
        res->next->val = l->val;
        if(flag) res->next->val += 1;
        if(res->next->val >= 10) {
            res->next->val -= 10;
            flag = true;
        } else {
            flag = false;
        }
        res = res->next;
        l = l->next;
    }
    if(flag) res->next = new ListNode(1);
    return head->next;
}

void getNext(vector<int>& next, const string& s) {
    int j = 0;
    next[0] = 0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[i] != s[j]) {
            j = next[j-1];
        }
        if(s[i] == s[j]) j++;
        next[i] = j;
    }
}

//! 3. 无重复字符的最长子串
int lengthOfLongestSubstring(string s) {
    if(s.size() <= 1) return s.size();
    unordered_set<char> cur_set;
    int left = 0, res = 0;
    for(int i=0; i<s.size(); i++) {
        while(cur_set.find(s[i]) != cur_set.end()) {
            cur_set.erase(s[left]);
            left++;
        }
        cur_set.insert(s[i]);
        res = max(res, i - left + 1);
    }

    return res;
}

//! 4. 寻找两个正序数组的中位数
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
}

//! 5. 最长回文子串
string longestPalindrome(string s) {
    string res {s[0]};
    for(int i=1; i<s.size(); i++) {
        int left = i - 1, right = i + 1;
        while(left >= 0 && right < s.size()) {
            if(s[left] != s[right]) break;
            left--;
            right++;
        }
        if((right - left - 1) > res.size()) res = s.substr(left + 1, right - left - 1);
        left = i - 1, right = i;
        while(left >= 0 && right < s.size()) {
            if(s[left] != s[right]) break;
            left--;
            right++;
        }
        if((right - left - 1) > res.size()) res = s.substr(left + 1, right - left - 1);
    }
    return res;
}

//! 11. 盛最多水的容器
int maxArea(vector<int>& height) {
    int res = 0;

    int i = 0, j = height.size() - 1;

    while(i < j) {
        if(height[i] < height[j]) {
            res = max(res, (j - i) * height[i]);
            i++;
        } else {
            res = max(res, (j - i) * height[j]);
            j--;
        }
    }

    return res;
}

//! 21. 合并两个有序链表
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* head = new ListNode;
    ListNode* node = head;

    while(list1 && list2) {
        if(list1->val < list2->val) {
            node->next = new ListNode(list1->val);
            list1 = list1->next;
            node = node->next;
        } else {
            node->next = new ListNode(list2->val);
            list2 = list2->next;
            node = node->next;
        }
    }

    ListNode* l = nullptr;

    if(list1) l = list1;
    if(list2) l = list2;

    while (l) {
        node->next = new ListNode(l->val);
        l = l->next;
        node = node->next;
    }

    return head->next;
}

//! 22.括号生成
vector<string> generateParenthesis(int n) {

}

//! 146. LRU缓存
class LRUCache {
private:
    list<pair<int,int>> cache;
    int _cap;
public:
    LRUCache(int capacity) {
        _cap = capacity;
        cache = list<pair<int,int>>(0);
    }

    int get(int key) {
        for(auto iter = cache.begin(); iter != cache.end(); iter++) {
            if(iter->first == key) {
                auto tmp = *iter;
                cache.erase(iter);
                cache.push_back(tmp);
                return tmp.second;
            }
        }
        return -1;
    }

    void put(int key, int value) {
        auto iter = cache.begin();
        for(; iter != cache.end(); iter++) {
            if(iter->first == key) break;
        }
        if(iter != cache.end() && iter->first == key) {
            iter->second = value;
            auto tmp = *iter;
            cache.erase(iter);
            cache.push_back(tmp);
        } else {
            if(cache.size() < _cap) {
                cache.push_back(make_pair(key, value));
            } else {
                cache.pop_front();
                cache.push_back(make_pair(key, value));
            }
        }
    }
};
//! 221. 最大正方形
int maximalSquare(vector<vector<char>>& matrix) {
    int res = 0;
    vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
    for(int i=0; i<matrix.size(); i++) {
        if(matrix[i][0] == '1') {
            dp[i][0] = 1;
            res = 1;
        }
    }
    for(int i=0; i<matrix[0].size(); i++) {
        if(matrix[0][i] == '1') {
            dp[0][i] = 1;
            res = 1;
        }
    }
    for(int i=1; i<matrix.size(); i++) {
        for(int j=1; j<matrix[0].size(); j++) {
            if(matrix[i][j] == '1') {
                if(dp[i-1][j-1] == 0) {
                    dp[i][j] = 1;
                } else {
                    bool flag = true;
                    int height = 0, width = 0;
                    for(int k=i; k >= i-dp[i-1][j-1]; k--, height++) {
                        if(matrix[k][j] != '1') {
                            flag = false;
                            break;
                        }
                    }
                    for(int k=j; k >= j-dp[i-1][j-1]; k--, width++) {
                        if(matrix[i][k] != '1') {
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = 1 + min(width - 1, height - 1);
                    }
                }
                res = max(res, dp[i][j] * dp[i][j]);
            }
        }
    }
    return res;
}

//! 287. 寻找重复数
int findDuplicate(vector<int>& nums) {
    int res = 0;
    for(int i=0; i<nums.size(); i++) {
        for(int j=i+1; j<nums.size(); j++) {
            if(nums[i] == nums[j]) return nums[i];
        }
    }
}

//! 581. 最短无序连续子数组
int findUnsortedSubarray(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while(left < nums.size() - 1 && nums[left] <= nums[left + 1]) {
        left++;
    }
    if(left == (nums.size() - 1)) return 0;
    while(right >= 0 && nums[right] >= nums[right - 1]) {
        right--;
    }
    int min_val = INT_MAX, max_val = INT_MIN;
    for(int i=left; i<=right; i++) {
        min_val = min(min_val, nums[i]);
        max_val = max(max_val, nums[i]);
    }

    int i = left - 1, j = right + 1;
    while(i >= 0 && nums[i] > min_val) i--;
    while(j < nums.size() && nums[j] < max_val) j++;

    return j - i - 1;
}

//! 394.字符串解码
string decodeString(string s) {
    string res;

    function<string(int&)> bfs = [&bfs, &s](int& id){
        string cur_res;
        for(int i=id; i<s.size(); i++) {
            if(s[i] >= '1' && s[i] <= '9') {
                vector<int> vec;
                while(s[i] != '[') {
                    vec.push_back(s[i] - '0');
                    i++;
                }
                int times = 0;
                int help = 1;
                for(int j=vec.size() - 1; j>=0; j--) {
                    times += help * vec[j];
                    help *= 10;
                }
                i = i + 1;
                auto tmp = bfs(i);
                while(times > 0) {
                    cur_res.append(tmp);
                    times--;
                }
            } else if(s[i] == ']') {
                id = i;
                break;
            } else {
                cur_res.push_back(s[i]);
            }
        }
        return cur_res;
    };

    for(int i=0; i<s.size(); i++) {
        if(s[i] >= '1' && s[i] <= '9') {
            vector<int> vec;
            while(s[i] != '[') {
                vec.push_back(s[i] - '0');
                i++;
            }
            int times = 0;
            int help = 1;
            for(int j=vec.size() - 1; j>=0; j--) {
                times += help * vec[j];
                help *= 10;
            }
            i = i + 1;
            auto tmp = bfs(i);
            while(times > 0) {
                res.append(tmp);
                times--;
            }
        } else {
            res.push_back(s[i]);
        }
    }
    return res;
}

//! 560. 和为 K 的子数组
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> dp;
    dp[0] = 1;
    int pre = 0, res = 0;
    for(int i=0; i<nums.size(); i++) {
        pre += nums[i];

        if(dp.find(pre - k) != dp.end()) {
            res += dp[pre - k];
        }
        dp[pre]++;
    }
    return res;
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//! 337. 打家劫舍 III
int rob(TreeNode* node) {
    function<vector<int>(TreeNode*)> dfs = [&dfs](TreeNode* node){
        if(!node) return vector<int>{0, 0};
        vector<int> left = dfs(node->left);
        vector<int> right = dfs(node->right);

        int val0 = max(left[0], left[1]) + max(right[0], right[1]);
        int val1 = node->val + left[0] + right[0];

        return vector<int>{val0, val1};
    };
    auto res = dfs(node);
    return max(res[0], res[1]);
}

//! 98. 打家劫舍
int rob(vector<int>& nums) {
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = max(nums[1], nums[0]);
    for(int i=2; i<nums.size(); i++) {
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp.back();
}

//! 322. 零钱兑换
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for(int i=0; i<coins.size(); i++) {
        for(int j=coins[i]; j<=amount; j++) {
            if(dp[j - coins[i]] != INT_MAX){
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

//! 238. 除自身以外数组的乘积
vector<int> productExceptSelf(vector<int>& nums) {

    vector<int> res(nums.size());

    res[0] = 1;

    for(int i=0; i<nums.size()-1; i++) {
        res[1 + i] = res[i] * nums[i];
    }

    int tmp = 1;

    for(int i=nums.size() - 1; i>=0; i--) {
        res[i] = res[i] * tmp;
        tmp = tmp * nums[i];
    }

    return res;
}

//! 114. 二叉树展开为链表
void flatten(TreeNode* node) {
    if(!node) return ;

    flatten(node->left);
    flatten(node->right);

    if(!node->left) return;

    TreeNode* tmp_right = node->right;
    TreeNode* tmp_left = node->left;
    node->left = nullptr;
    node->right = tmp_left;

    TreeNode* tmp_left_end = tmp_left;
    while(tmp_left_end->right) {
        tmp_left_end = tmp_left_end->right;
    }
    tmp_left_end->right = tmp_right;

    return;
}

//! 128. 最长连续序列
int longestConsecutive(vector<int>& nums) {
    int res = 1;
    unordered_set<int> bs;
    for(auto num : nums) {
        bs.insert(num);
    }
    for (const int &num : bs) {
        if(bs.find(num - 1) == bs.end()){
            int cur_num = num;
            int cur_res = 1;
            while (bs.find(cur_num + 1) != bs.end()) {
                cur_num++;
                cur_res++;
            }
            res = max(res, cur_res);
        }
    }

    return res;
}

//! 152. 乘积最大子数组
int maxProduct(vector<int>& nums) {
    vector<vector<int>> all_neg_pos;
    vector<int> cur_neg_pos;
    vector<int> all_zero_pos;
    all_zero_pos.push_back(-1);
    all_neg_pos.push_back(cur_neg_pos);
    int res = INT_MIN;
    for(int i=0; i<nums.size(); i++) {
        if(nums[i] < 0) cur_neg_pos.push_back(i);
        if(nums[i] == 0) {
            all_zero_pos.push_back(i);
            all_neg_pos.push_back(cur_neg_pos);
            cur_neg_pos.clear();
        }
    }

    all_neg_pos.push_back(cur_neg_pos);
    all_zero_pos.push_back(nums.size());

    for(int i=1; i<all_zero_pos.size(); i++) {
        if(all_neg_pos[i].size() % 2 == 0) {
            if(all_zero_pos[i-1] + 1 < nums.size()) {
                int cur_res = nums[all_zero_pos[i-1] + 1];
                for(int j=all_zero_pos[i-1] + 2; j<all_zero_pos[i]; j++ ) cur_res *= nums[j];
                res = max(res, cur_res);
            }
        } else {
            int cur_res_1 = nums[all_zero_pos[i-1] + 1];
            for(int j=all_zero_pos[i-1] + 2; j<all_neg_pos[i].back(); j++ ) cur_res_1 *= nums[j];
            res = max(res, cur_res_1);
            if(all_neg_pos[i].front() + 1 < nums.size()) {
                int cur_res_2 = nums[all_neg_pos[i].front() + 1];
                for(int j=all_neg_pos[i].front() + 2; j<all_zero_pos[i]; j++ ) cur_res_2 *= nums[j];
                res = max(res, cur_res_2);
            }
        }
    }

    return res;
}

//! 148. 排序链表
ListNode* sortList(ListNode* head) {
    ListNode* node = head;
    vector<int> vec;
    while(node) {
        vec.push_back(node->val);
        node = node->next;
    }
    sort(vec.begin(), vec.end());
    node = head;
    auto iter = vec.begin();
    while(node) {
        node->val = *iter;
        node = node->next;
        iter++;
    }
    return head;
}

//! 79. 单词搜索
bool exist(vector<vector<char>>& board, string word) {
    int n = board.size();
    int m = board[0].size();
    bool visited[n][m];
    function<bool(int, int, int)> dfs = [&](int idx, int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || board[x][y] != word[idx]) return false;
        if(idx == (word.size() - 1)) return true;

        visited[x][y] = true;
        bool res = false;
        res |= dfs(idx+1, x, y-1);
        if(res) return true;
        res |= dfs(idx+1, x+1, y);
        if(res) return true;
        res |= dfs(idx+1, x, y+1);
        if(res) return true;
        res |= dfs(idx+1, x-1, y);

        visited[x][y] = false;
        return res;
    };
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            memset(visited,0,sizeof visited);
            if(dfs(0, i, j)) return true;
        }
    }
    return false;
}



//! 75. 颜色分类
void sortColors(vector<int>& nums) {
    int red = 0;
    int white = 0;
    int blue = 0;
    for(auto num : nums) {
        if(num == 0) {
            red++;
        } else if(num == 1) {
            white++;
        } else {
            blue++;
        }
    }
    for(int i=0; i<red; i++) {
        nums[i] = 0;
    }
    for(int i=red; i<red + white; i++) {
        nums[i] = 1;
    }
    for(int i=red+white; i<nums.size(); i++) {
        nums[i] = 2;
    }
}

//! 136. 只出现一次的数字
int singleNumber(vector<int>& nums) {
    int res = 0;
    for(const auto& num : nums) {
        res = res ^ num;
    }
    return res;
}

//! 121. 买卖股票的最佳时机
int maxProfit(vector<int>& prices) {
    int profit = 0, cost = INT_MAX;
    for(const auto &price : prices) {
        cost = min(cost, price);
        profit = max(profit, price - cost);
    }
    return profit;
}

//! 169. 多数元素
int majorityElement(vector<int>& nums) {
    int cur_num = INT_MIN, cur_count = 0;
    for(const auto & num : nums) {
        if(num != cur_num) {
            if(cur_count == 0) {
                cur_count = 1;
                cur_num = num;
            } else {
                cur_count--;
            }
        } else {
            cur_count++;
        }
    }
    return cur_num;
}

//! 234. 回文链表
bool isPalindrome(ListNode* head) {
    function<ListNode*(ListNode*)> reverse = [](ListNode* head){
        ListNode* cur_head = head;
        ListNode* cur_node = head;
        while (cur_node && cur_node->next) {
            ListNode* tmp = cur_node->next->next;
            cur_node->next->next = cur_head;
            cur_head = cur_node->next;
            cur_node->next = tmp;
        }
        return cur_head;
    };

    ListNode* fast = head, *slow = head, *left, *right, *right_head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    if(fast) {
        right = reverse(slow->next);
    } else {
        right = reverse(slow);
    }
    left = head;
    right_head = right;

    while(right) {
        if(right->val != left->val) return false;
        right = right->next;
        left = left->next;
    }

    right_head = reverse(right_head);
    return true;
}

//! 338. 比特位计数
vector<int> countBits(int n) {
    if(n == 0) return {0};
    if(n == 1) return {0,1};
    if(n == 2) return {0,1,1};
    if(n == 3) return {0,1,1,2};
    vector<int> res(n+1);
    res[0] = 0;
    res[1] = 1;
    res[2] = 1;
    res[3] = 2;

    int bits = 3;
    while(1) {
        int prev_start = pow(2, bits - 2);
        int cur_start = pow(2, bits - 1);
        int next_start = pow(2, bits);
        int i = 0;
        while((cur_start - 1) > (prev_start + i)) {
            res[cur_start + i] = res[prev_start + i];
            if(cur_start + i == n) return res;
            i++;
        }
        int j = 0;
        while(next_start > (cur_start + i)) {
            res[cur_start + i] = res[prev_start + j - 1] + 1;
            if(cur_start + i == n) return res;
            i++;
            j++;
        }
        bits++;
    }
}

//! 461. 汉明距离
int hammingDistance(int x, int y) {
    int xor_res = x ^ y;
    int res = 0;
    for(int i=0; i<32; i++) {
        if((xor_res >> i) & 0x1) res++;
    }
    return res;
}

vector<int> findDisappearedNumbers(vector<int>& nums) {
    for(int i=0; i<nums.size(); i++) {
        if(nums[abs(nums[i]) - 1] > 0) {
            nums[abs(nums[i]) - 1] *= -1;
        }
    }
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        if(nums[i] > 0) res.push_back(i+1);
    }
    return res;
}

void quicksort(vector<int>& nums, int low, int high) {
    function<int(vector<int>&, int, int)> part = [](vector<int>& nums, int low, int high){
        int pivot = nums[low];
        while(low < high) {
            while(low < high && nums[high] > pivot) {
                high--;
            }
            if(low < high) {
                int tmp = nums[low];
                nums[low] = nums[high];
                nums[high] = tmp;
                low++;
            }
            while(low < high && nums[low] <= pivot) {
                low++;
            }
            if(low < high) {
                int tmp = nums[low];
                nums[low] = nums[high];
                nums[high] = tmp;
                high--;
            }
        }
        return low;
    };
    if(low < high) {
        int mid = part(nums, low, high);
        quicksort(nums, low, mid - 1);
        quicksort(nums, mid + 1, high);
    }
}

//! 437. 路径总和 III
int pathSum(TreeNode* root, int targetSum) {
    int res = 0;
    function<void(TreeNode*, int)> dfs = [&dfs, &res, &targetSum](TreeNode* node, int sum){
        if(sum == targetSum) res++;
        if(!node) return;
        dfs(node->left, sum + node->val);
        dfs(node->right, sum + node->val);
        dfs(node->right, sum + node->val);
        dfs(node->right, sum + node->val);
    };
    dfs(root, 0);
    return res;
}

//! 139. 单词拆分
bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    for (int i=1; i<s.size(); i++) {
        for(int j=i; j>=0; j--) {
            if(dp[j] && std::find(wordDict.begin(), wordDict.end(), s.substr(j, i - j)) != wordDict.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp.back();
}

//! 104. 二叉树的最大深度
int maxDepth(TreeNode* root) {
    if(!root) return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

//! 64. 最小路径和
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for(int i=1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for(int i=1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
    for(int i=1; i < m; i++) {
        for(int j=1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

//! 48. 旋转图像
void rotate(vector<vector<int>>& matrix) {

}

//! 34. 在排序数组中查找元素的第一个和最后一个位置
vector<int> searchRange(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, medium, right = n - 1;
    vector<int> res(2, -1);
    while(left <= right) {
        medium = (left + right) / 2;
        if(nums[medium] > target) {
            right = medium - 1;
        } else if(nums[medium] < target) {
            left = medium + 1;
        } else {
            res[0] = medium;
            right = medium - 1;
        }
    }
    left = 0;
    right = n - 1;
    while(left <= right) {
        medium = (left + right) / 2;
        if(nums[medium] > target) {
            right = medium - 1;
        } else if(nums[medium] < target) {
            left = medium + 1;
        } else {
            res[1] = medium;
            left = medium + 1;
        }
    }
    return res;
}

//! 101. 对称二叉树
bool isSymmetric(TreeNode* root) {
    function<bool(TreeNode*, TreeNode*)> func = [&func](TreeNode* l, TreeNode* r) {
        if(!l && !r) return true;
        if(l && r && l->val == r->val) {
            return func(l->left, r->right) && func(l->right, r->left);
        } else {
            return false;
        }
    };
    return func(root->left, root->right);
}

bool hasCycle(ListNode *head) {
    ListNode* fast = head, *slow = head;
    while(fast && slow) {
        if(fast->next) {
            fast = fast->next->next;
        } else {
            return false;
        }
        slow = slow->next;
        if(fast == slow) return true;
    }
    return false;
}

//! 647. 回文子串
int countSubstrings(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    dp[0][0] = true;
    int res = 1;

    for(int i=1; i<n; i++) {
        for(int j=0; j<=i-2; j++) {
            if(dp[j+1][i-1] && s[j] == s[i]) {
                dp[j][i] = true;
                res++;
            }
        }
        if(s[i-1] == s[i]) {
            dp[i-1][i] = true;
            res++;
        }
        dp[i][i] = true;
        res++;
    }

    return res;
}

class UnionFind {
private:
    vector<int> parent; // 存放父节点
    vector<double> weight; // 指向父节点的权值
public:
    UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
            weight.push_back(1.0); // 权重初始化为1
        }
    }
};

    //! 399. 除法求值
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    vector<double> res(queries.size(), -1);
    int n = equations.size();
    // 初始化并查集
    UnionFind unionFind(2 * n);

    // 第 1 步：预处理，将变量的值与 id 进行映射
    map<string, int> hashMap;
    int id = 0;
    for (int i = 0; i < n; ++i) {
        // 存分子，分母，值为id
        vector<string> equation = equations[i];
        string var1 = equation[0];
        string var2 = equation[1];
        if (!hashMap.count(var1)) {
            hashMap[var1] = id;
            ++id;
        }
        if (!hashMap.count(var2)) {
            hashMap[var2] = id;
            ++id;
        }
        // 把分子分母用有向边连起来

    return res;
}
#endif //LEETCODE_HOT100_H
